// 方案三：原地翻转
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;

    // 水平翻转
    for (int row = 0; row < n / 2; row++) {
        for (int col = 0; col < n; col++) {
            int tmp = matrix[row][col];
            matrix[row][col] = matrix[n - row - 1][col];
            matrix[n - row - 1][col] = tmp;
        }
    }

    // 主对角线翻转
    for (int row = 0; row < n; row++) {
        // bug 修复：到 row 为止即可，要不然就翻转回来了
        for (int col = 0; col < row; col++) {
            int tmp = matrix[row][col];
            matrix[row][col] = matrix[col][row];
            matrix[col][row] = tmp;
        }
    }
}

// 方案二：原地旋转
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
void rotate2(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;
    for (int row = 0; row < n / 2; row++) {
        for (int col = 0; col < (n + 1) / 2; col++) {
            int tmp = matrix[row][col];
            matrix[row][col] = matrix[n - col - 1][row];
            matrix[n - col - 1][row] = matrix[n - row - 1][n - col - 1];
            matrix[n - row - 1][n - col - 1] = matrix[col][n - row - 1];
            matrix[col][n - row - 1] = tmp;
        }
    }
}

// 方案一：使用额外数组
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
void rotate1(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;
    int newMatrix[n][n];

    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            newMatrix[col][n - row - 1] = matrix[row][col];
        }
    }

    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            matrix[row][col] = newMatrix[row][col];
        }
    }
}